from collections import deque
from typing import List


class Solution:
    """
    方法：使用深度优先搜索（DFS）遍历网格，遇到'1'时进行岛屿计数，并通过DFS标记所有相连的陆地

    Args:
        grid: List[List[str]] - 由'0'（水）和'1'（陆地）组成的二维网格

    Returns:
        int - 岛屿的数量

    Time: O(M*N) - 需要遍历整个网格，M和N分别是网格的行数和列数
    Space: O(M*N) - 递归调用栈的深度，最坏情况下可能需要遍历整个网格
    """
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        m, n = len(grid), len(grid[0])
        count = 0

        directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    queue = deque([(i, j)])
                    grid[i][j] = '2'
                    while queue:
                        x, y = queue.popleft()
                        for dx, dy in directions:
                            nx, ny = x + dx, y + dy
                            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
                                grid[nx][ny] = '2'
                                queue.append((nx,ny))

        return count

    """
    方法：使用广度优先搜索（BFS）遍历网格，遇到'1'时进行岛屿计数，并通过BFS标记所有相连的陆地

    Args:
        grid: List[List[str]] - 由'0'（水）和'1'（陆地）组成的二维网格

    Returns:
        int - 岛屿的数量

    Time: O(M*N) - 需要遍历整个网格，M和N分别是网格的行数和列数
    Space: O(min(M,N)) - 队列在最坏情况下可能存储对角线上的所有元素
    """
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        m, n = len(grid), len(grid[0])
        count = 0

        directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    queue = deque([(i, j)])
                    grid[i][j] = '2'
                    while queue:
                        x, y = queue.popleft()
                        for dx, dy in directions:
                            nx, ny = x + dx, y + dy
                            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
                                grid[nx][ny] = '2'
                                queue.append((nx,ny))

        return count
     
   